public class FindMinMoves {

    public int findMinMoves(int[] machines) {
        int n = machines.length;
        int sum = 0;
        int[] pre = new int[n];
        int[] order = new int[n];
        for (int i = 0; i < n; i++) {
            sum += machines[i];
        }
        if (sum % n != 0) return -1;
        int avg = sum / n;
        sum = machines[0];
        for (int i = 1; i < n; i++) {
            pre[i] = sum - i * avg;
            sum += machines[i];
        }
        sum = machines[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            order[i] = sum - (n - i - 1) * avg;
            sum += machines[i];
        }
        int[] temp = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (pre[i] < 0 && order[i] < 0) {
                temp[i] = Math.abs(pre[i]) + Math.abs(order[i]);
            } else {
                temp[i] = Math.max(Math.abs(pre[i]), Math.abs(order[i]));
            }
            ans = Math.max(ans, temp[i]);
        }
        return ans;
    }
}
